package Solution_2;

public class Solution {
    public int postIndex;
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val) {
            this.val = val;
        }
    }
    public TreeNode buildTree(int[] inorder,int[] postorder) {
        postIndex = postorder.length - 1;
        return buildTreeChild(postorder,inorder,0,postIndex-1);
    }
    //用中序遍历 和 后序遍历 来创建二叉树
    public TreeNode buildTreeChild(int[] postorder,int[] inorder,int Begin,int End) {
        if(Begin > End) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[postIndex]);
        int rootIndex = findIndex(inorder,Begin,End,postorder[postIndex]);
        postIndex--;
        //创建二叉树 后序遍历 -》 左 右 根
        root.right = buildTreeChild(postorder,inorder,rootIndex+1,End);
        root.left = buildTreeChild(postorder,inorder,Begin,rootIndex-1);
        return root;
    }
    public int findIndex(int[] inorder,int Begin,int End,int key) {
        for (int i = Begin; i <= End; i++) {
            if(inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }
}
